package com.leetCode.problem;


/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-11-08 10:42:30
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-11-08     张李鑫                     1.0         1.0 Version
 */
public class Problem124 {
    /**
     * 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
     * <p>
     * 路径和 是路径中各节点值的总和。
     * <p>
     * 给你一个二叉树的根节点 root ，返回其 最大路径和 。
     */

    public static class Info {
        private int max;

        public Info(int max) {
            this.max = max;
        }

        @Override
        public String toString() {
            return "Info{" +
                    "max=" + max +
                    '}';
        }
    }

    public int min = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        Info process = process(root);
        return Math.max(process.max, min);
    }

    public Info process(TreeNode root) {
        if (root == null) {
            return new Info(0);
        }
        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);

        int headMax = root.val;
        if (leftInfo.max != Integer.MIN_VALUE) {
            headMax += leftInfo.max;
        }
        if (rightInfo.max != Integer.MIN_VALUE) {
            headMax += rightInfo.max;
        }
        min = Math.max(min, headMax);

        int max = Math.max(leftInfo.max, rightInfo.max) + root.val;

        return new Info(max);
    }
    public int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;

        // 更新答案
        min = Math.max(min, priceNewpath);

        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }



    public static void main(String[] args) {
        Problem124 problem124 = new Problem124();
        TreeNode treeNode = new TreeNode(-2);
        treeNode.left = new TreeNode(-1);
        treeNode.right = new TreeNode(-2);
        System.out.println(problem124.maxGain(treeNode));
        System.out.println(problem124.maxPathSum(treeNode));
    }

}
